This invention relates to navigation systems and location based information delivery. Specifically, this invention relates to a method and system for delivering interactive and real-time navigational information using distributed navigation information processing and mobile telephones.
Many navigation systems are based on satellite-based global positioning system (GPS) devices which have been applied in automobile navigation systems, see, e.g., U.S. Pat. Nos. 5,938,720, 5,928,307, 5,922,042, 5,912,635, 5,910,177, 5,904,728, 5,902,350, all incorporated herein by reference for all purposes. Such automobile navigation systems, however, are expensive and inconvenient to use. Many such systems are further not appropriate for walking. Therefore, there is a great need in the art to incorporate navigation systems in personal handheld devices.
However, there are several technical obstacles that prevent the incorporation of navigational capabilities in handheld devices for providing turn-by-turn real-time navigation services. One such obstacle is the amount of geographic data needed to provide reasonably detailed navigational information. Small handheld devices include cellular phones, personal digital assistants, or computers, however, the amount of embedded memory is limited and is impractical to store a large amount of geographic information. In existing automobile navigation systems, GPS systems are employed to provide information about the location and movement of a user. Geographic information is usually stored in a geographic mapping database stored on a CD-ROM, hard-disk drive device or other large capacity storage medium.
Another obstacle is that the lack of information processing power of small devices such as those mentioned above. For example, the information processing power of a cellular telephone is typically provided by an embedded microprocessor with limited memory. While the information processing power of embedded microprocessors is generally increasing, such processors are still not suitable for processor intensive real-time navigational tasks.
An additional obstacle is the insufficient location accuracy provided by current technology. Initial sources of inaccuracy of the GPS based systems, for example, are either imposed by the U.S. Department of Defense through Selective Availability (S/A), other sources of error are due to atmospheric and timing errors limiting the accuracy of a single GPS receiver to +/xe2x88x9250 meters. Methods exist which can be used to enchance accuracies to +/xe2x88x925 meters. Such methods include Enhanced GPS systems (i.e., SnapTrack) and network based system (i.e., Truepoint). These methods use a known position, such as a survey control point, as a reference point to correct the GPS position error. These methods of correcting GPS positions are referred to as Differential GPS or DGPS. The DGPS corrections can be applied to the GPS data in real-time using data telemetry (radio modems). Toward expanding the use of DGPS, the United States and Candian Coast Guard are establishing a series of radio beacons to transmit the DGPS corrections for accurate navigation along the Great Lakes, the Mississippi River and tributaries, the Gulf Coast, and the Eastern and Western coasts of North America. However, such radio beacons are not available to consumers traveling in most inland locations.
Location information that is ambiguous due to a number of factors discussed above makes navigational systems difficult to develop. For example, if the user is driving in a downtown area with streets spaced close together, a GPS location within +/xe2x88x9250 meters is not adequate to give turn-by-turn directions. The GPS location information is thus considered ambiguous and inappropriate for navigation systems. In other situations, a GPS location within +/xe2x88x9250 meters is adequate for navigation purpose. For example, if a user is driving on a highway in a remote area without any nearby exits, the GPS location is sufficient for calculating further navigation directions. Thus, in such a situation, the GPS location is not ambiguous.
Current automobile GPS navigation systems make use of other sensors, such as accelerometers, speedometers, etc. plus some sophisticated filtering technology to improve the accuracy of a navigational system (see, e.g., U.S. Pat. No. 5,912,635, previously incorporated by reference for all purposes). In addition, many automobile-based navigational systems use map-aiding technology as well. However, for a navigational system implemented using handheld devices such as cellular telephones, it is impractical to have the handheld devices connected to external sensors, especially when the device is used while walking.
Accordingly, it would be desirable to provide a navigational system that provides accurate navigational instructions. It would further be desirable to provide a navigational system that can be implemented on an existing infrastructure and is adaptable to new infrastructures as they become available.
It would further be desirable to provide a navigational system that can be implemented on handheld devices with limited computational power as well as devices with enhanced computational power.
It would further be desirable to provide a navigational system that can make use of many forms of real time information to provide accurate location calculations as well as optimal navigation paths.
These and other objects are provided for by a system and method for interactive real-time distributed navigation. In an embodiment of the invention, a user advantageously makes use of an often under-utilized sensorxe2x80x94a user""s eyes. Toward reducing an ambiguity associated with a location derived from a positional sensor, the present invention prompts for and utilizes a user""s input. In an embodiment, a consolidated list of candidate locations are presented to a user. A user""s selection from such list is then used to correct for errors in other position detecting sensors.
In another embodiment of the invention, an enhanced and simplified dynamic real-time navigation system is provided based upon distributed computing and database systems. In such a manner, wireless devices with limited computational power interact with distributed servers that execute any necessary intensive processing. In another embodiment, geographic map information databases are advantageously stored on distributed servers with large storage capacity.
In another embodiment, depending upon the capability of a user""s device, data storage and navigation calculation load are dynamically distributed between the server and the device. In an embodiment, a user sends a request to navigate from a current location (or point A) to point B. A server, after receiving the request (including destination information) and user""s location, the system of the present invention generates a global navigation route across several small geographic areas. The server then sends navigational information relating to a first small geographic area to the user""s device. Once the user moves out of the first small geographical area, the information will be updated by the server either at the request of the user""s device or initiated by the server based upon the location of the user.
Another aspect of the invention provides navigation guidance based on real-time traffic conditions. The traffic information can be obtained from a group of navigational service users, by observing their speeds and making comparisons with the nominal street speed limits in a map database. This traffic information assists the system to determine an optimal route for its users in real-time. At each juncture, the system will dynamically determine an optimal path to get to the destination based on the traffic information. The best route can be defined based on the user""s request, for example, it can be either time or gas consumption which will be minimized.
Another embodiment of the invention provides directions in a queue ahead of time. This is particularly important for wireless device navigation because of the small screen. For example, the server prompts, either by voice or text, xe2x80x9cyou are going to see University Ave. in about 5 minutes (or 500 yards), where you should turn right.xe2x80x9d In the mean time, if not necessary, the communication link can be released to reduce the server traffic.
Yet another embodiment of the invention provides for warm/cold start operation. In a warm start situation, a position is assumed not to be ambiguous such that a navigational session is immediately provided to a user. In such a warm start situation, however, a method is provided for assuring that a warm start session is appropriate. Where appropriate, the warm start session continues. Where not appropriate, the warm start session reverts to methods for removing ambiguity of a user""s location. Where a cold start session is selected, a method of the invention checks whether conditions for a warm start are met. Where warm start conditions are met, a user""s position is not ambiguous such that a navigational session is immediately provided to the user.